# 方法一：暴力模拟
class Solution:
    def intToRoman(self, num: int) -> str:
        has = {1: "I", 5: "V", 10: "X", 50: "L", 100: "C", 500: "D", 1000: "M"}
        ans = ""
        i = 0
        while num:
            cur = num % 10
            cnt = cur * (10 ** i)
            if cur == 4 or cur == 9:
                # 减法
                base = 10 ** i
                if cur == 4:
                    ans +=has[5 * base]+has[base]
                else:
                    ans +=has[10 * base]+has[base]
            else:
                # 加法
                c=""
                for k, v in sorted(has.items(), reverse=True):
                    if k <= cnt:
                        count = cnt // k
                        cnt -= count * k
                        c+= v * count
                ans+=c[::-1]
            num //= 10
            i += 1
        return ans[::-1]

# 方法二：技巧
class Solution:
    def intToRoman(self, num: int) -> str:
        hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
        ans = ''
        for key in hashmap:
            if num//key != 0:
                count = num//key
                ans += hashmap[key]*count
                num %= key
        return ans